#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/11 18:41
# ===========================================
#       题目名称： 90. 子集 II
#       题目地址： https://leetcode.cn/problems/subsets-ii/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================


class Solution:
    def subsetsWithDup(self, nums):
        """
            通过字典进行实现 key 剩余的元素  v 上一次没排序完的元素
        """
        sub_sets = [[]]  # 子集
        ss_dict = dict()
        for i in range(len(nums)):
            temp_nums = nums.copy()
            del temp_nums[i]
            ss_dict[tuple(temp_nums)] = (nums[i],)
        temp_sub_sets = list(set(ss_dict.values()))
        temp_sub_sets.sort()
        sub_sets.extend(temp_sub_sets)
        while ss_dict:
            temp_ss_dict = dict()
            for k, v in ss_dict.items():
                k = list(k)
                for i in range(len(k)):
                    temp_k = k.copy()
                    del temp_k[i]
                    temp_val = v + (k[i],)
                    temp_val = list(temp_val)
                    temp_val.sort()
                    temp_ss_dict[tuple(temp_k)] = tuple(temp_val)
            temp_sub_sets = list(set(temp_ss_dict.values()))
            temp_sub_sets.sort()
            sub_sets.extend(temp_sub_sets)
            ss_dict = temp_ss_dict

        return sub_sets

    def subsetsWithDup3(self, nums):
        """
            实现错误
        """
        sub_sets = []  # 子集
        temp_sets = set()
        for i in range(len(nums)):
            digits = 0
            while digits <= len(nums):
                temp_nums = nums[i:digits]
                temp_nums.sort()
                temp_sets.add(tuple(temp_nums))
                digits += 1
        temp_sets = list(temp_sets)
        sub_sets = [list(item) for item in temp_sets]
        return sub_sets

    def subsetsWithDup2(self, nums):
        """
            内存超限
        """
        sub_sets = [[]]  # 子集
        digits = 0  # 位数
        digits_sub_dict = {}  # key () v 剩余的
        while digits < len(nums):
            if not digits_sub_dict:
                for i in range(len(nums)):
                    temp_nums = nums.copy()
                    del temp_nums[i]
                    digits_sub_dict[(nums[i],)] = temp_nums
                    sub_sets.append([nums[i], ])
            else:
                temp_digits_sub_sets = {}
                for k, v in digits_sub_dict.items():
                    for i in range(len(v)):
                        temp_v = v.copy()
                        del temp_v[i]
                        temp_digits_sub_sets[k + (v[i],)] = temp_v
                        sub_sets.append(list(k + (v[i],)))
                digits_sub_dict = temp_digits_sub_sets
            digits += 1
        sub_sets = set([tuple(sorted(item)) for item in sub_sets])
        sub_sets = list([list(item) for item in sub_sets])
        return sub_sets


if __name__ == '__main__':
    s = Solution()
    # [[],[1],[1,2],[1,2,2],[2],[2,2]]
    print(s.subsetsWithDup(nums=[1, 2, 2]))
    # [[],[0]]
    print(s.subsetsWithDup(nums=[0]))
    # [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
    print(s.subsetsWithDup(nums=[1, 2, 3]))
